package com.justnow.offer;

import java.util.ArrayList;
import java.util.List;

public class Solution34 {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> list=  new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if (root == null) return res;
        dfs(root, sum);
        return res;
    }

    private void dfs(TreeNode root, int sum) {
        if (root == null) return;
        sum -= root.val;
        list.add(root.val);
        if (sum == 0 && root.left == null && root.right == null)
            //res.add(new ArrayList<>(list));
            res.add(list);
        dfs(root.left, sum);
        dfs(root.right, sum);
        //当root为叶子点时，不管是不是满足要求的路径，都需要将叶子节点剔除掉，然后再进入该叶子节点的父节点的递归中，
        //开始判断父节点的另一个叶子节点是否满足题目中的需求
        list.remove(list.size() - 1);
    }

    public static void main(String[] args) {
        TreeNode node10 = new TreeNode(10);
        TreeNode node5 = new TreeNode(5);
        TreeNode node12 = new TreeNode(12);
        TreeNode node4 = new TreeNode(4);
        TreeNode node7 = new TreeNode(7);
        node10.left = node5;
        node10.right = node12;
        node5.left = node4;
        node5.right = node7;

        Solution34 solution34 = new Solution34();
        List<List<Integer>> lists = solution34.pathSum(node10, 22);
        for (List<Integer> list : lists) {
            System.out.println();
            for (Integer integer : list) {
                System.out.print(integer + "、");
            }
            System.out.println();
        }

    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int val) {
        this.val = val;
    }

}
